package q803_hitBricks;

import CommonClass.UF;

public class Solution {
    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int rows, cols;
    /*
    此题是一个逆向思维解题的过程，并且用了并查集
    因为按照顺序打掉砖块并计算影响的数量很难
    所以先将所有hits中的砖块都打碎并构建并查集，然后逆序的一个个恢复砖块
    看每次恢复时候并查集中与屋顶相连的那个簇出现了什么变化，也就是本题的答案
     */
    public int[] hitBricks(int[][] grid, int[][] hits) {
        // 二维数组的clone和一维的不一样，变成浅拷贝，所以不能用clone
        // int[][] copy = grid.clone();
        rows = grid.length;
        cols = grid[0].length;
        // 1 第一步 创建复制数组 并将所有hits标记砖块提前打碎
        int[][] copy = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                copy[i][j] = grid[i][j];
            }
        }
        for (int[] hit : hits) {
            copy[hit[0]][hit[1]] = 0;
        }

        // 2 创建UF 但是大小要设置为size + 1 这是由于存在一个特殊的位置：房顶
        // 所以将所有与roof相连的0层砖头连接到屋顶上 也就是用size号元素代替房顶
        // 然后用copy数组中所有相连的砖块构建并查集
        int size = rows * cols;
        UF uf = new UF(size + 1);
        for (int i = 0; i < cols; i++) {
            if (copy[0][i] == 1) {
                uf.union(i, size);
            }
        }
        // 由于是顺序遍历 所以只考察每个砖左边和上面的情况即可
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (copy[i][j] == 1 && copy[i - 1][j] == 1) {
                    uf.union(getIndex(i, j), getIndex(i - 1, j));
                }

                if (j > 0 && copy[i][j] == 1 && copy[i][j - 1] == 1) {
                    uf.union(getIndex(i, j), getIndex(i, j - 1));
                }
            }
        }
        int[] res = new int[hits.length];
        // 3 逆序的恢复砖头 然后每次恢复时先记录此时屋顶这个簇的大小 然后恢复后再计算该簇的大小
        // 差值就是这次打掉砖块导致消失的砖头数量
        // 注意 要倒序遍历hits 代表逐渐恢复每一个砖头
        for (int i = hits.length - 1; i >= 0; i--) {
            int x = hits[i][0], y = hits[i][1];
            // 如果原来的数组中这个位置本来就是0 代表这个位置移除砖头与否都没用
            if (grid[x][y] == 0) continue;

            int curSize = uf.getSize(size);
            // 注意 如果恢复的砖块直接与屋顶相连 那么首先要将其连接到屋顶的簇上
            // 例如
            // ---------
            //     1
            //     2
            // 在屋顶上垂直的连了两个砖 而1是被移除的那个 如果恢复时不先考虑其与屋顶的相连
            // 就计算不了实际上移除它所引起的变化
            if (x == 0) uf.union(y, size);
            // 然后再考察其与其他砖头的连接
            for (int[] dir : dirs) {
                int next_x = x + dir[0], next_y = y + dir[1];
                if (isValid(next_x, next_y) && copy[next_x][next_y] == 1) {
                    uf.union(getIndex(next_x, next_y), getIndex(x, y));
                }
            }

            int afterRecover = uf.getSize(size);
            // max代表最少也是0
            res[i] = Math.max(0, afterRecover - curSize - 1);
            copy[x][y] = 1;
        }
        return res;
    }

    private boolean isValid(int next_x, int next_y) {
        return next_x >= 0 && next_y >= 0 && next_x < rows && next_y < cols;
    }

    /*
    这里涉及到用一个数来表示在矩阵中位置的方法：
    首先需要了解，此题中用了通用的UF模版，该模版中对于union指的是对于两个int数代表的元素进行合并
    例如947合并时，是对一个数组中的不同石头进行合并，对于第i块和第j块石头，就使用union(i, j)
    但是此题是一个二维数组，所以有必要将其转换为用一个数字能够表示的方式，最简单的方法就是按从左到右从上到下
    从(0, 0)坐标开始标记为0，最后一个就标记为size - 1，此时getIndex就是i * cols + j
    例如坐标(1, 2)就是第二行第三列的元素，此时i就代表经过了i行，而每行的长度则是cols
    所以应该是i * cols + j 但如果按照从上到下从左到右计算也可以 那就是i * rows + j
     */
    private int getIndex(int i, int j) {
        return i * cols + j;
    }
}
